#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
public:
	unordered_map<string, bool> memory;
	bool wordBreak(string s, vector<string>& wordDict) {
		if (s == "")
			return true;
		else if (memory.count(s))
			return false;
		bool result = false;
		for (int i = 0; i < s.size(); i++) {
			auto it=find(wordDict.begin(), wordDict.end(), s.substr(0, i + 1));
			if (it != wordDict.end()) {
				result = result || wordBreak(s.substr(i+1),wordDict);
				if (!result)
					memory[s.substr(i + 1)] = false;
			}
		}
		return result;
	}
};

int main() {
	Solution s;
	string st = "1234567";
	string str = "aaaaaaa";
	vector<string> arr = { "aaaa", "aaa" };
	cout << st.substr(0,1);
	if (s.wordBreak(str, arr))
		cout << "1" << endl;
	else cout << "2" << endl;
}